Packet scheduling is necessary when multiple packets compete for a common outgoing communications link (e.g., a physical communications link or a pseudo-wire). This scenario occurs commonly in routers (and other network elements). At its most simplest, a router connects a first network with a second network. That is, there is a first physical communications link that connects a first network interface of the router to the first network and a second physical communications link that connects a second network interface of the router to the second network, thereby enabling the router to route packets between the two networks. The router may receive from the first network via the first physical communications link packets destined for a node in the second network. At certain points in time, the rate at which these packets arrive at the router may exceed the rate at which the router can transmit packets onto the second physical communications link (e.g., the second physical communications link may have a lower bandwidth than the first physical communication link). Thus, the router may employ packet queues to temporarily store the received packets. Thus, at any given point in time, it is likely that the router is storing multiple packets in its packet queues that were received from the first network and destined for the second network. As there may be a single physical communications link connecting the router to the second network, the queued packets all “compete” for this common outgoing physical communications link. As such, the router requires some method of packet scheduling. That is, the router needs some way to select which of the queued packets will be next in line for outgoing transmission.
One packet scheduling technique involves (a) creating a scheduling tree having a root scheduling node, a set of leaf scheduling nodes and zero or more aggregate scheduling nodes, where each leaf scheduling node is associated with a packet queue, and (b) employing a scheduling engine to, on a continuous basis, traverse the scheduling tree to arrive at a leaf scheduling node and to move a packet from the packet queue associated with the leaf scheduling node to a transmit queue. A problem with this technique is that the performance of the scheduling engine may be limited due to, among other things, memory bandwidth limitations and contention overhead for accessing and updating the shared state information of each scheduling node.
What is desired, therefore, is an improved packet scheduling process.